﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 算法基本功.算法._0_数组._1_双指针.左右指针.二分搜索
{
    /// <summary>
    /// 左边界的意思是最左边符合target的 右边界同理
    /// </summary>
    internal class 二分搜索_左右边界
    {
        public int Binary_LeftBound(int[] nums, int target) {
            //边界检查
            if (nums.Length == 0 || target < nums[0] || target > nums[nums.Length - 1]) {
                return -1;
            }

            int left=0,right =nums.Length - 1;
            while (left <= right) { 
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
                    right = mid - 1;
                } 
                else if (nums[mid] > target) {
                    right = mid - 1;
                }
                else if (nums[mid] < target) { 
                    left = mid + 1;
                }
            }
            //left的位置是逻辑上最可能存在目标值的位置 因此可能有目标值不存在的情况
            return nums[left] == target ? left : -1;
        }



        public int Binary_RightBound(int[] nums, int target)
        {
            //边界检查
            if (nums.Length == 0 || target < nums[0] || target > nums[nums.Length - 1])
            {
                return -1;
            }

            int left = 0, right = nums.Length - 1;
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target)
                {
                    left = mid + 1;
                }
                else if (nums[mid] > target)
                {
                    right = mid - 1;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
            }
            //left的位置是逻辑上最可能存在目标值的位置 因此可能有目标值不存在的情况
            return nums[right] == target ? right : -1;
        }
    }
}
